﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<stdbool.h>
using namespace std;

class Answer
{
public:
    int myAtoi(string str)
    {
        bool sign = true;
        //默认为正数

        // 跳过开头可能存在的空格
        int i = 0;
        while (i < str.size() && str[i] == ' ')
        {
            i++;
        }

        //接着判断首个字符是否为正负号
        if (str[i] == '-')
        {
            sign = false;
            // 该字符串为负数，移至下一个字符接着判断
            i++;
        }
        // 字符串为正数，sign已经默认为true，直接移动到下一位即可
        else if (str[i] == '+')
        {
            i++;
        }

        //下面开始对非正负符号位进行判断
        if (str[i] < '0' || str[i] > '9') // 正常数字第一位不能是0，必须为1~9之间的数字，否则就是非法数字
            return 0;

        int res = 0;
        //这里res用的int型，需要更加仔细考虑边界情况，但如果用long的话可以省去一些麻烦
        int num = 0;
        int border = INT_MAX / 10;
        // 用来验证计算结果是否溢出int范围的数据
        while (i < str.size())
        {
            // 遇到非数字字符，则返回已经计算的res结果
            if (str[i] < '0' || str[i] > '9')
                break;

            // 注意这句话要放在字符转换前，因为需要验证的位数比实际值的位数要少一位, 这里比较巧妙的地方在于
            // 1. 用低于int型数据长度一位的数据border判断了超过int型数据长度的值 
            // 2. 将超过最大值和低于最小值的情况都包括了
            if (res > border || res == border && str[i] > '7')
                return sign == true ? INT_MAX : INT_MIN;

            //开始对数字字符进行转换
            num = str[i] - '0';
            res = res * 10 + num;
            i++;
        }

        //最后结果根据符号添加正负号
        return sign == true ? res : -res;
    }
};

/*
该题有多种解题思路，比如：
  1. 统计每个数字出现的次数，然后找出只出现1次的数字，缺点：需要借助辅助空间
  2. 对数据进行排序，然后找出只出现1次的数字，缺点：时间复杂度不是O(N)
而题目要求了，时间复杂度必须为O(N)线性时间复杂度，因此便增加了题目的难度。


题目说：只有一个数字出现一次，其余数字均出现3次，假设数组为{3,5,3,3}
通过分析可知：
3的二进制：0 0 0 0 0 0 1 1
5的二进制：0 0 0 0 0 1 0 1
3的二进制：0 0 0 0 0 0 1 1
3的二进制：0 0 0 0 0 0 1 1
          0 0 0 0 0 1 3 4  二进制1的总数
对于出现3次的数字，各位出现的次数都是3的倍数，因此对统计的为1的比特总数%3
          0 0 0 0 0 1 0 1 = 5
          结果就是只出现一次的数字
*/


// 时间复杂度：O(32*N)--->O(N)  空间复杂度：O(1)
class Stardard_Answer_Two
{
public:
    int singleNumber(vector<int>&nums) 
    {
        int ans  = 0;
        for (int i  = 0; i  < 32; ++i) 
        {


            // 统计该每个数字第i个比特位为1的总数
            int total  = 0;
            for (int num: nums) 
            {
                total  += ((num >> i) & 1);
            }


            // 如果total能够被3整除，说明只出现一次的数字在该位置上一定是0
            // 否则在该位置上一定是1
            if (total  % 3) 
            {
                ans  |= (1 << i);
            }
        }
        return ans;
    }
};

class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        vector<vector<int>> v(2);
        //int x = 0;
        long long int x = 0;
        // for(int i = 0;i < nums.size();++i)
        // {
        //     x = nums[i];
        //     vector<int>::iterator it = find(v[0].begin(),v[0].end(),x);
        //     if(it != v[0].end())
        //     {
        //         v[0].push_back(x);
        //     }
        // }

        for (int i = 0; i < nums.size(); ++i)
        {
            x = nums[i];
            vector<int>::iterator it = find(v[0].begin(), v[0].end(), x);

            if (it == v[0].end())
            {
                v[0].push_back(x);
                v[1].push_back(0);
            }
        }

        for (int i = 0; i < nums.size(); ++i)
        {
            x = nums[i];
            vector<int>::iterator it = find(v[0].begin(), v[0].end(), x);

            if (it != v[0].end())
            {
                ++v[1][it - v[0].begin()];
            }
        }
       
        for (int i = 0; i < v[0].size(); ++i)
        {
            if (v[1][i] == 1)
            {
                return v[0][i];
            }
        }
        return x;
    }
};

int main()
{
    Solution s;
    int tmp[] = { 2,2,3,2 };
    vector<int> v;
    size_t size = sizeof(tmp) / sizeof(tmp[0]);
    v.reserve(sizeof(tmp) / sizeof(tmp[0]));
    for(int i = 0;i < size;++i)
    {
        v.push_back(tmp[i]);
    }
    int x = s.singleNumber(v);
    cout << x;

    return 0;
}